GCD Property of the Division Algorithm

Proof

To prove the above, we proceed by showing independently that $gcd(a,b)\le gcd(b,r)$ and $gcd(a,b)\ge gcd(b,r)$.

Let $g_1=gcd(a,b)$. By definition $g_1\mid a$ and $g_1\mid b$. From this, $g_1\mid bq$ and therefore $g_1\mid bq-a=r$. This means that $g_1$ is a common divisor of $b$ and $r$, but not necessarily the greatest. Hence

We then make a similar argument in the opposite direction. Let $g_2=gcd(b,r)$. By definition $g_2\mid b$ and $g_2\mid r$. From this, $g_2\mid bq$ and therefore $g_2\mid bq+r=a$. This means that $g_2$ is a common divisor of $a$ and $b$, but not necessarily the greatest. Hence:

Combining the above results proves equality: